The Hero

Memory limit: 256 MB

Byteotheus, most famous Byteotian hero, once again emerged victorious from the battle. While his crew are loading the ship up with the acquired valuables, in his cabin, Byteotheus plans his way back to his homeland island-The Bitaca. It is not an easy task. Many gods envy Byteotheus popularity among the people and gladly would take him down a peg or two. Fortunately, some of them look favourably on him, especially goddess Bythena. It was none other but her that sent Byteotheus a dream last night, warning him of the dangers that he could encounter.

There are islands on the Byteonian Sea. It will be convenient to number those from 1 to . Presently Byteotheus's ship is at island 1, and its destination is The Bitaca-island . In some cases two islands are joined by one-way sea routes, additionally each of those islands is a start point for maximum of 10 sea routes. We are numbering the sea routes from 1 to ; -th route leads from island , to island , and it takes exactly days to cover it. In case the ship set sail on -th route, starting from island at dawn on day, it will reach its destination island at dawn, at day . The ship can stop at any island for an indefinite period before moving on again. However, before reaching a successive island, it cannot deviate off the set path, and sail no longer that is required to cover the particular route. Byteotheus can start his voyage from island 1 at dawn on the first day, at the earliest.

The goddess Bythena warning has been very precise. She provided Byteotheus an exact list of traps, prepared by the gods. Every trap is situated on a certain island and is active for a certain time period. To be more precise, the -th trap is located on the island and is active from the day until and including the day . The traps are really dangerous-in case Byteotheus's ship finds itself on an island with an active trap, no one will survive. Luckily his homeland Bitaca is free from traps, and no traps on the island 1 are active on the first day.

Obviously Byteotheus wants to plan his way home, to avoid all traps. He wonders, however, how much longer he would need for his voyage because of them. Help him and indicate the minimum number of days necessary to safely return to Bitaca.

Input

The first line of input contains two integers and (, ): the number of islands and the number of sea routes. Subsequent lines describe the sea routes: included in the -th there are three integers , , (, , ), indicating that the -th route leads from island to island and it takes days. All routes are one way. Every island is a start point for maximum of 10 sea routes.

The next line contains integer (), describing the number of the traps. Next lines hold the description of the traps: in the -th line there are three integers , , (, ), indicating that the -th trap is located on the island and is active from the day until and including the day . If , then .

Output

In case it is not possible to plan the route avoiding all the traps, the one and only line should output word NIE (Polish for no). In the opposite case, an integer should be output describing the minimum number of days required to finalise the voyage (the ship reaches Bitaca on the day at sunrise).

Example

For the input data:

5 6
1 2 3
1 4 13
2 3 1
2 4 2
3 2 2
4 5 1
5
1 2 4
1 8 8
2 6 7
2 10 11
4 6 7

the correct result is:

10

Explanation to the example: Byteotheus set sail from island 1 on the first day, at sunrise. He arrives on island 2 on the fourth day. There he waits one day and starts off for island 3. After getting there on the sixth day, he immediately turns back to island 2, where from he travels in the direction of island 4 on the eighth day. He arrives there on the tenth day and finally reaches Bitaca on the eleventh day.

Task author: Tomasz Idziaszek